package com.code.leetcode.before50;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Stack;

/**
 * @author codeDorado
 * @version 1.0
 * @date 2020/7/25 16:09
 */
public class The84_stack_sentinal {
    public int largestRectangleArea(int[] heights) {
        int len = heights.length;
        if (len < 1) return 0;
        if (len == 1) return heights[0];
        int max = 0;
        int[] ints = new int[len + 2];
        for (int i = 0; i < len; i++) {
            ints[i + 1] = heights[i];
        }
        len = len + 2;
        heights = ints;
        Deque<Integer> stack = new ArrayDeque<Integer>();
        stack.addLast(0);
        for (int i = 1; i < len; i++) {
            while (heights[stack.peekLast()] > heights[i]) {
                int height = heights[stack.removeLast()];
                int width = i - stack.peekLast() - 1;
                max = Math.max(max, height * width);
            }
            stack.addLast(i);
        }
        return max;
    }
}
